package 算法.十大排序算法;

import java.util.Arrays;

/**
 * @author coderFu
 * @create 2022/3/18
 * 堆排序
 * 首先根据情况，升序还是降序
 * 升序， 采用大顶堆
 * 降序， 采用小顶堆
 * 步骤 1、先生产所需的大顶堆或者小顶堆
 * 步骤2、将顶部元素和最后的元素进行替换
 * 注意： 要先找到大顶堆， 然后进行交换数据，交换后再次排序。
 *        直到完成所有的排序。
 */
public class CoderHeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{123,12,33,45,6,7,8,6,44,43,455};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr){


        //1.构建大顶堆,让所有的根节点都是较大的值
        // 最后一个根节点： root = arr,length-1/2-1;
        //
        for(int i=arr.length/2-1;i>=0;i--){

            //从第一个非叶子结点从下至上，从右至左调整结构
            heapSort(arr,i,arr.length);
        }
        // 构建大顶堆
        for(int j=arr.length-1; j>0; j--){
            swap(arr,0,j);
            heapSort(arr,0,j);
        }
    }
    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void heapSort(int[] arr, int i, int length){
        // 拿到根节点元素
        int temp = arr[i];
         //从i结点的左子结点开始，也就是2i+1处开始
        // 注意下一次跳到的位置 是下一个根的位置
        for(int k=i*2+1;k<length;k=k*2+1){
            //如果左子结点小于右子结点，k指向右子结点
            if(k+1<length && arr[k]<arr[k+1]){
                k++;
            }
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            if(arr[k] >temp){
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;
    }
}
